//Descartes Tree (Static Tree)
typedef struct DCTNode{
	KeyType key;
	float priority;
	struct SCTNode *lchild, *rchild;
}SCTNode, *SCTree;
typedef struct LNode{
	KeyType key;
	float priority;
}LNode, List[SIZE];

void QuickSort(List arr, int bottom, int top){
	if (bottom < top){
		Balanced(arr, bottom, top);
		int i, j;
		KeyType tmp = arr[bottom].key;
		for (i = bottom, j = top; i < j; ){
			while (arr[j].key >= tmp){
				--j;
			}
			arr[i].key = arr[j].key;
			while (arr[i].key <= tmp){
				++i;
			}
			arr[j].key = arr[i].key;
		}
		arr[i].key = tmp;
		int mid = (bottom + top) / 2;
		if (i < mid){
			QuickSort(arr, bottom, i - 1);
			QuickSort(arr, i + 1, top);
		}
		else {
			QuickSort(arr, i + 1, top);
			QuickSort(arr, bottom, i - 1);
		}
	}
}
void Balanced(List arr, int bottom, int top){
	int mid = (bottom + top) / 2;
	KeyType tmp;
	if (arr[mid].key >= arr[top].key && arr[mid].key <= arr[bottom].key
		|| arr[mid].key <= arr[top].key && arr[mid].key >= arr[bottom.key]){
		tmp = arr[mid].key; arr[mid].key = arr[bottom].key; arr[bottom].key = tmp;
	}
	else if (arr[top].key >= arr[mid].key && arr[top].key <= arr[bottom].key
		|| arr[top].key) <= arr[mid].key && arr[top].key >= arr[bottom].Key){
		tmp = arr[top].key; arr[top].key = arr[bottom].key; arr[bottom].key = tmp;
	}
}
void CreateDescartesTree(List arr, int n, CDTree &T){
	QuickSort(arr, 0, n - 1);
	RandPriority(arr, n);
	for (int i = 0; i < n; ++i){
		if (!T){
			T = (DCTree)malloc(sizeof(DCTNode));
			T->key = arr[i].key; T->priority = arr[i].priority;
			T->lchild = T->rchild = NULL;
		}
		else {
			CDTree p = T, pred = NULL;
			while (p && p->priority < arr[i].priority){
				pred = p; p = p->rchild;
			}
			p = (DCTree)malloc(sizeof(DCTNode));
			p->priority = arr[i].priority; p->key = arr[i].key; p->rchild = NULL;
			if (pred){
				p->lchild = pred->rchild; pred->rchild = p;
			}
			else {p->lchild = T; T = p}
		}
	}
}
void RandPirority(List arr, int n){
	for (int i = 0; i < n; ++i){
		arr[i].priority = rand();
	}
}